package com.leetcode.practice.quesions;

import com.leetcode.practice.interfaces.IQuestion;

/**
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

	示例 1：

	输入: "babad"
	输出: "bab"
	注意: "aba" 也是一个有效答案。
	示例 2：

	输入: "cbbd"
	输出: "bb"

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/longest-palindromic-substring
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author Administrator
 *
 */
public class q3_最长回文字符串  implements IQuestion{

	String str="babad";

	@Override
	public void solution() {
		// TODO Auto-generated method stub
		solution2();
	}

	/**
	 * 暴力法
	 * 
	 * 時間複雜度：O(n^3)
	 * 空間複雜度：O(1)
	 */
	private void solution1() {
		String result="";
		for(int i=0;i<str.length()-1;i++) {
			for(int j=i+1;j<str.length();j++) {
				String asc=str.substring(i, j);
				if(asc.equals(descStr(asc))) {
					if(asc.length()>result.length()) {
						result=asc;
					}
				}
			}
		}
		System.out.println("最大回文序列->"+result);
	}
	
	private String descStr(String s) {
		StringBuilder sb=new StringBuilder();
		for(int i=s.length()-1;i>=0;i--) {
			sb.append(s.charAt(i));
		}
		return sb.toString();
	}
	
	/**
	 * 中心擴展法
	 * 
	 */
	private void solution2() {
		int start=0,end=0;
		int maxLength=0;
		for(int i=0;i<str.length();i++) {
			int length1=expandCenter(str,i,i); // 中心有一個的情況
			int length2=expandCenter(str,i,i+1); // 中心有兩個的情況
			int length=Math.max(length1, length2);
			if(length>maxLength) {
				maxLength=length;
				start=i-(length-1)/2;
				end=i+length/2;
			}
		}
		String result=str.substring(start,end+1);
		System.out.println("最大回文序列->"+result);
	}
	
	private int expandCenter(String s,int left,int right) {
		int L=left,R=right;
		while(L>=0 && R<s.length() && s.charAt(L)==s.charAt(R)) {
			L--;
			R++;
		}
		return R-L-1;
	}

	public static void main(String[] args) {
		q3_最长回文字符串 q3=new q3_最长回文字符串();
		q3.solution();
	}
}
